# _*_ utf-8 _*_
# 了解插入排序法的原理与实现
import random
"""
    插入排序的原理为：
        1、将待排序的列表的看作两部分（首元素是一个有序的列表，其他元素为无序列表，遍历无序列表，将无序列表中的元素插入到有序列表中，使有无序列表变成有序的列表）
        2、实现的步骤：
            1、记录下待插的元素，第一轮为列表中的第二个元素
            2、从第一个元素，到待插元素的下标为止，找到插入位置，将待插元素插入到插入位置（也即，如果第二个元素比第一个元素大，插入位置为第二个元素的下标，如果第二个元素比
                                                                            第一个元素小，插入位置为第一个元素的下标）
            3、重复上面的操作
"""
lst = [random.randint(1, 100) for i in range(20)]

print("排序前：", lst)

# 使用插入排序对lst进行排序
for i in range(1, len(lst)):
    current_element = lst[i]                        # 记录下待插元素
    j = i - 1                                       # 从子列表中的第一个元素开始循环
    while j >= 0 and lst[j] > current_element:      # 进行循环找到比待插元素还小的位置，找到插入位置
        lst[j + 1] = lst[j]
        j -= 1
    lst[j + 1] = current_element
print("排序后：", lst)




